In the production of standard-cell integrated-circuit chips, a designer first attempts to obtain a logical representation of the function the chip is to perform. The end result of the logic design is a netlist providing the necessary interconnections to boxes representing logic elements selected from a library. Upon completion of the logic design, a physical design must then be performed to translate the abstract logic design into its physical realization on the chip. The first step in the physical design process consists of placing boxes, wherein physical realizations of the library cells are used to place the boxes on a chip image. The placement must be legal, i.e., have no overlaps and must meet the technology constraints. After placement, some logic optimization is typically done, followed by the insertion of clocks. Thereafter, the design is routed, such that the netlist inter- connections between the boxes are realized as wire segments on the image.
The placement step endeavors to place the boxes while leaving enough room for routing the wires. In general, placement follows some model of how this routing is to be accomplished, but the model is not exact and does not always predict the actual routes. Placement is therefore unable to guarantee that the boxes will be placed in a manner such that all of the wires will be routed. In addition, some boxes may represent functions requiring a large number of inputs/outputs, which may preclude placing them in a way that encourages ratability, unless the design is very sparse. The reason why the chip cannot be routed is that the number of wires that are to be routed in a given area exceeds the space allocated for this purpose.
When all the wires cannot be routed, the chip will not perform the desired function and, thus, will not be manufacturable. A standard way of correcting unrouted wires is for the designer to use a physical editor to manually route or reroute the missing wires. This is a time consuming and expensive process, since in today's large chips it is not unusual to find thousands of wires that cannot be routed. In addition, in the event that an error is found in the logical design, this fix-up step may need to be repeated several times.
The method described herein attempts to avoid the problem of unwireable chips by performing logic restructuring of the design to encourage routability. In order to describe the inventive method, several definitions must first be provided.
Wiring congestion occurs when the number of wire passing through an area of the circuit design exceeds the space available for wiring. As previously mentioned, when wiring congestion occurs, the design cannot be manufactured. Thus, the congestion must be corrected. The current state-of-the-art is that the designer, using physical editing software tools, manually corrects these errors.
The present method makes use of the logic function of the circuit design referred to netlist (also referred to as network) that consists of a directed graph wherein the nodes represent boxes and the edges represent wires (alternately, nets). Each box carries with it the Boolean function it computes (e.g. AND, NOT, NOR, XOR, MUX, and the like) and a physical realization of that function in terms of transistors. These physical realizations have known attributes, such as size, aspect ratio and speed. Boxes also have pins which provide connecting points to the nets. For example, a box representing a two-input AND box has two input pins and one output pin. When the physical placement of the box occurs, the pins are implicitly placed since they are part of the physical realization of the box.
A subset of boxes within the network consisting of one box or a set of boxes interconnected by nets from the network is referred to as a sub-network of the network.
The way the boxes and nets are interconnected customizes the logic function that the chip is to compute. An output pin connected to a net is referred to as its source. The net may be connected to one or more input pins, all of which are referred to as sinks. The number of sinks of a given net is called the fan-out.
The present method applies to clocked circuits. Timing of the circuits provides a slack at each pin. The late mode slack (or simply slack) is the difference between the time at which a value must arrive at a pin and the actual time of arrival (the time when a stable signal value at the pin is reached). If the slack is negative (or less than a specified threshold), the signal arrives too late and the net or pin is called critical. If the slack is positive (or larger than a specified threshold), the net or pin is designated non-critical. If the slack at one pin is larger than the slack at another pin, the slack at the first pin is called less critical than the slack at the second pin. An early mode slack may be similarly defined as the difference between the earliest time that a signal can arrive at a pin (i.e., begin to change from its previous stable state) and the earliest time at which it is allowed to arrive.
Every circuit has a set of constraints it must meet. These constraints include timing constraints, which specify when clock and other signals actually arrive and when they are required to arrive, as described above. Additional constraints include electrical constraints, which limit the amount of capacitance on any net and the maximum amount of slew time that can be tolerated. Finally, there are other technology rules that constrain the design. For example, as mentioned above, placed boxes must not overlap. A design is considered to be legal if it meets all the design constraints.
It is the task of the placement to embed the physical realization of the boxes into the chip image in such a way that they obey technology constraints. For instance, the physical realizations of the boxes must not overlap. A placement consists of assigning to each box an (x,y) coordinate within the chip image, viewed as an array. It is a goal of placement to place the design so that wiring congestion is minimized. Placement programs use a variety of techniques to predict congestion. The most common is to simply minimize the total wire length in the design, since less wire usually means less congestion. In some cases, more elaborate methods of congestion prediction are used, but no known method guarantees that the outcome of the placement will always be routed without congestion.
It is the task of routing (alternately also referred to as wiring) to arrange the wires on the chip image so that connections among the pins match the logical connections. Chips typically have several metal layers upon which the wires are routed with the horizontal wires routed on different layers than the vertical wires. Then, a via is required to bring the net of one layer to another. The routing program must therefore produce a list of horizontal and vertical segments for each net, separated by vias, all of which conform to the technology requirements for wire spacing and wire capacity.
Routing is usually divided into two processes: a global wiring and a detailed wiring. In a global wiring, a grid system is overlayed on the chip image. Each square of the grid is referred to as a tile (also referred to as wiring tile) and the perimeter of the tile is formed by the four edges, i.e., on the north, south, east and west of the tile. Tiles are said to be adjacent when they share an edge. Boxes whose (x,y) coordinates are within the tile form part of the tile. Global routing routes the wires in the design from edge to edge according to logic requirements and technology rules, but it does not route from the edge of the grid to the pins of the boxes contained within the tile. It is, therefore, the task of detailed wiring to route from the tile edges to the pins and to assign metal layers and wiring positions.
FIG. 1 illustrates the aforementioned concepts. Shown therein is a conceptual representation of a chip as seen by the logic optimization, placement and routing. The chip origin is positioned at coordinate (xl,yl) and its upper right hand corner at (xh,yh). The area of the chip is overlaid with a wiring grid (dashed lines), the open squares are wiring tiles and the dashed lines are edges. The chip has two boxes, i.e., ‘a’, a two-input AND with one output placed at (xa,ya), and ‘b’, an inverter (NOT) with one input and one output at (xb,yb). The large black dots indicate pins. There is a net, ‘t’, between box ‘a’ and box ‘b’. The global route for net ‘t’ is shown by the small cross-hatched rectangle (Note: the route stops at the edges of the wiring tiles, and does not go directly to the pins of boxes ‘a’ and ‘b’). The complete detailed route for ‘t’ is shown by a solid line.
The logic structure of the design may be changed according to the normal rules of Boolean algebra. This is called logic restructuring. Method of logic restructuring fall into four groups:                1. Logic decomposition takes a more complex function and breaks it down into component parts. This changes the structure of the logic, but not its function. By way of example, a single box may compute an AND-OR function (e.g., ab+cd). Then, the logic restructuring decomposes it into three boxes, an AND of ‘a’ and ‘b’ (ab), an AND of ‘c’ and ‘d’ (cd), and the OR of the output of the two AND boxes. Another example of a logic decomposition is taking a 6-way OR (a+b+c+d+e+f) and breaking it into a three-way OR (a+b+c) and OR'ing the output of the new box with the remaining terms from the original box (d, e and f), thereby creating a 3-way OR feeding a 4-way OR.        2. Logic recomposition is the opposite operation of logic decomposition. In the above examples, two ANDs (ab and cd) feeding an OR collapse into an AND-OR combination (ab+cd). The 3-way OR feeding a 4-way OR collapses into a 6-way OR. When performing a logic recomposition, it is important to handle multiple fan-outs properly.        3. Rewiring (also referred to as connection rearrangement or pin swapping) takes advantage of the ability to move the connection of nets to pins in the logic without changing the logic function. For instance, rewiring takes advantage of the commutative property of some logic functions (e.g., AND, NAND, NOR, OR, XOR, XNOR, and the like) by moving nets among the pins of commutative functions. In the previous OR example, a+b+c+d+e+f can be interchangeably written as f+b+c+d+e+a. Therefore, if net a is connected to pin 1 of the OR box, and net f to pin 6, then, the rewire causes net f to move to pin 1 and net a to pin 6. This rearrangement can be performed even if the logic has been decomposed, as described above. The pin rearrangement is not limited to commutative functions, since more advanced analysis can determine rearrangements beyond commutativity.        4. Repowering consists of three types of moves: resizing, buffering and cloning. In resizing, the box physical realization changes while keeping the Boolean function constant. In buffering, the fan-out of a net is reduced by adding buffers (single-input/single-output identity functions) or inverter pairs on a net. In cloning, the source box of the net is duplicated and the sinks of the net are distributed among the original box and its clone.        
All of the above methods are used for reducing the congestion. In addition, once the design is placed, congestion is further reduced by moving a box from one wiring tile to another.
In most cases, wiring is performed after the chip placement. Thus, the wire end points are known and fixed. Routing (or wiring) programs attempt to completely route the wires among the end points to avoid congestion. Routing programs are divided in two phases: a global phase which routes wires to the edges of a grid positioned over the design, and a detailed wiring which completes the routes from the grid edges to the cell pins forming the design. The detailed router also assigns tracks and layers, as appropriate to the design style of the circuit. Given a global route, it is not always possible to achieve a detailed route because the routes cannot be completed from the grid edge to the pins. This is referred to pin congestion and will not be addressed by the present method, which relates only to congestion due to the global routes.
In some instances, wiring may be advantageously performed concurrently with placement, particularly since the placements in the design can to some extent avoid wiring congestion. While this alleviates certain congestion problems, the simultaneous placement and routing systems do not guarantee uncongested designs and provide no recourse when global congestion occurs.
Attempts have been made to restructure logic to improve wireability. In some cases, pre-routing (and, sometimes, pre-placement) metrics are used to restructure the design in areas where congestion is predicted by the metrics. These methods are not guaranteed to improve congestion. Since they work with estimates that often do not reflect the actual wire routes, they may optimize the wrong areas and, sometimes, increase wiring congestion. In other cases, a congested area is identified after routing and reimplemented in ways that improve wiring congestion. These methods are guaranteed to generate a different design, but not necessarily a more wirable one.
It is important to note that global congestion is often caused by a combination of terminated wires, where the wire enters a grid and terminates on the pin(s) of cell(s) within the grid, and feed-through wires, where the wire crosses adjacent wiring grids without making a connection to any logic circuits within the grid. A weakness of both of the above restructuring methods is that they improve wiring in the region selected, but have no affect on global wires because they do not take into consideration the effect of feedthrough wires. In these cases, the only solutions are: (a) to cause some terminated wires to be routed outside the selected region which, by definition, these methods cannot achieve, or (b) cause rerouting of the feedthrough wires by adding logic elements (e.g., buffers) to certain areas outside the congested region. Since these wires do not appear within the original region to be restructured, this kind of restructuring will not find solutions of the kind described in (a) and (b).
The aforementioned methods do not guarantee an improvement of the wireability of a design because global congestion is a function of placement, of the logic structure of the design and of the quality of the router. It is possible that a design placement and logic structure will preclude a successful routing, but this cannot be determined until the routing is actually completed. Estimates (e.g., rectilinear Steiner routes) do not provide sufficient detail and/or correlation with true routes to accurately predict congestion prior to the actual routing. Furthermore, none of the above restructuring methods address the problems of relieving wiring congestion in the presence of other design constraints. Even if the restructuring methods succeed in reducing congestion, it is achieved at the expense of adding timing, electrical, or power violations. Correcting these violations entails modifying the size or structure of the logic or adding new logic elements, all of which must be replaced and rerouted, often causing new congestion problems. Thus, it is not evident that the restructuring methods described above converge to a correct design.
In addition to the above restructuring methods, there are other known methods that address the problem of pin congestion in a detailed wiring. These include: swapping commutative pins on a single logic cell, and moving placed and routed logic by sliding cells into adjacent circuit rows or columns to allow more wiring room into the pins of the cells. Such methods are effective in improving the detailed wiring, but they do not address global congestion issues. Indeed, they are guaranteed not to affect global wiring.